linearity of expectation

2022 SCPC 2차 5번문제가 이거 쓴다는데 전혀 못풀겠었다. 두 확률변수 X와 Y에 대해 E(X+Y)=E(X)+E(Y) 라는 간단한 공식이다. 중요한건, X와 Y가 독립일 필요가 전혀 없다는것이다!!! 아래 링크의 AB*CD 예제를 풀어보면 무슨말인지 알것이다. https://brilliant.org/wiki/linearity-of-expectation/

이걸통해 이제 문제에서 구하라는 기댓값을 확률변수 X로 둘때, 그걸 더 간단한 확률변수들 X0,X1,... 들의 합으로 표현한 후에 각각의 기댓값을 구해서 합치는 접근이 가능해진다. 쪼갠 변수가 더 쪼개질 수 있다면 재귀적으로 표현될것이고, 쪼갯을때 겹치는 확률변수가 존재할수 있으니 DP가 종종 나오게 되는것같다. 쪼갤때 독립적인 확률변수로 쪼개려면 비트마스킹도 필요하고 막 답이없는데 독립일 필요가 없어서 매우 유용할것 같다.

NOTE: E(XY)=E(X)E(Y)는 독립변수일때만 가능한걸 주의하자. 기댓값의 선형성을 활용하기 위해 확률변수를 분해하는 방법이 중요한데 이러한 분해방법에 대한 직관력은 위 글에서 답 나와있는 연습문제들을 풀면서 기를 수 있을것 같다. 몇개만 풀어봤는데도 정말 도움 많이됨.